package com.mango.algorithm.sort;

import com.google.common.base.Stopwatch;

import java.util.Arrays;
import java.util.concurrent.TimeUnit;

/**
 * 冒泡排序
 * 空间复杂度：O(1)
 * 时间复杂度：O(n2)
 * 思路：
 * 2重循环，内循环数比较外层值小于内层值，则交换；如果内层比较完了没有出现交换则说明已经排好顺序，则提前退出。
 */
public class BubbleSort {
    public static void main(String[] args) {
        Stopwatch sw = Stopwatch.createStarted();
        int[] nums = {1,7,4,6,9,24,12};
        System.out.println("old:"+Arrays.toString(nums));
        System.out.println("result:"+Arrays.toString(sort(nums))+"耗时:"+sw.elapsed(TimeUnit.MILLISECONDS)+"ms");
    }
    // 冒泡排序
    public static int[] sort(int[] nums){
        boolean hasChanged = true;
        for(int i=0;i<nums.length && hasChanged;i++){
            hasChanged = false;
            for(int j=0;j<nums.length;j++){
                if(nums[i] < nums[j]){
                    swap2(nums,i,j);
                    hasChanged = true;
                    System.out.println(i+")"+Arrays.toString(nums));
                }
            }
        }
        return nums;
    }
    // 交换数组下标
    public static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 异或交换，前提是i和j不指向同一内存地址
    public static void swap2(int[] nums,int i,int j){
       nums[i] = nums[i] ^ nums[j];
       nums[j] = nums[i] ^ nums[j];
       nums[i] = nums[i] ^ nums[j];
    }
}
